package leetcode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-23 14:36
 **/
public class LeetCode1047 {

    /**
     * 使用了LinkedList作为栈的数据结构解决该题
     * @param s
     * @return
     */
    public String removeDuplicates2(String s) {
        Deque<Character> stack = new LinkedList<>();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if (stack.isEmpty()) {
                stack.push(s.charAt(i));
                continue;
            }
            if (stack.peek() == s.charAt(i)) {
                stack.pop();
                continue;
            }
            stack.push(s.charAt(i));
        }
        String str = "";
        while (!stack.isEmpty()) {
            str = stack.pop() + str;
        }
        return str;
    }

    /**
     * 使用了StringBuilder作为栈的数据结构解决此题
     * @param s
     * @return
     */
    public String removeDuplicates3(String s) {
        StringBuilder builder = new StringBuilder("");
        int len = s.length();
        //用来标识StringBuilder的栈顶
        int top = -1;
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (top >= 0 && c == builder.charAt(top)) {
                builder.deleteCharAt(top);
                top--;
            } else {
                builder.append(c);
                top++;
            }
        }
        return builder.toString();
    }

    public String removeDuplicates(String s) {
        char[] chars = s.toCharArray();
        //用来标识当前字符数组不相邻重复的元素的最大下标
        int top = -1;
        for (int i = 0; i < chars.length; i++) {
            if (top == -1 || chars[i] != chars[top] ) {
                chars[++top] = chars[i];
            } else {
                top--;
            }
        }
        return String.valueOf(chars, 0, top + 1);
    }
}
